package DataStructure.tree;

import DataStructure.tree.TreeNode;

/**
 * 98. 验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree/
 * 题目简述：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 */
public class IsValidBST {

    /**
     * 思路：二叉搜索树的中序遍历序列一定是严格递增的，因此通过递归中序遍历检查相邻元素是否递增即可（用一个全局变量记录前一个元素值）
     */
    long cur = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (cur >= root.val) return false;
        cur = root.val;
        return isValidBST(root.right);
    }
}
